import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[]array={1,9,2,8,3,7,4,6,5};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void heapSort(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            siftDown(array, parent, array.length - 1);
        }
        int end = array.length-1;
        while(end>0){
           swap(array,0,end);
           siftDown(array,0,end);
           end--;
        }
    }

    private static void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] =tmp;
    }

    private static void siftDown(int[] array, int parent, int end) {
       int child = parent*2+1;
       while(child<end){
           if(child+1<end&&array[child+1]>array[child]){
               child++;
           }
           if(array[child]>array[parent]){
               swap(array,child,parent);
               parent = child;
               child =  parent*2+1;
           }else {
              break;
           }
       }
    }
}
